class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.max_diameter = 0  # 存储最大直径

        def depth(node):
            if not node:
                return 0
            left_depth = depth(node.left)  # 左子树深度
            right_depth = depth(node.right)  # 右子树深度
            # 更新当前节点的最大路径长度（左右深度之和）
            self.max_diameter = max(self.max_diameter, left_depth + right_depth)
            # 返回当前节点的深度（左右较大者 + 自身）
            return max(left_depth, right_depth) + 1

        depth(root)  # 触发递归计算
        return self.max_diameter



    def diameterOfBinaryTree2(self, root: TreeNode) -> int:
        if not root:
            return 0

        max_diameter = 0
        stack = []
        # 用于存储节点对应的深度值
        depth_map = {}

        # 初始化栈，元组格式：(节点, 是否已访问)
        stack.append((root, False))

        while stack:
            node, visited = stack.pop()

            if not node:
                continue

            if visited:
                # 后序遍历处理位置
                left_depth = depth_map.get(node.left, 0)
                right_depth = depth_map.get(node.right, 0)

                # 计算当前节点为根的路径长度
                max_diameter = max(max_diameter, left_depth + right_depth)

                # 存储当前节点深度（左右子树较大值 +1）
                depth_map[node] = max(left_depth, right_depth) + 1
            else:
                # 压栈顺序：当前节点（标记已访问）→ 右 → 左
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))

        return max_diameter

# 测试
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)


s = Solution()
print(s.diameterOfBinaryTree(root))